#include <common.h>

int4* input;
int4* end;
int4* idx1;
int4* invt;

int4 items[MAX_KEY_NUM * 2];
int4* lst;


/**
 * function declarations
 */
void init();
inline int find_mid(const int tag, int4* arr, int l, int h);
inline int intersection(int len1, int4* lst1, int len2, int4* lst2);
inline void intersection(int4 *a, int al, int ah, int4 *b, int bl, int bh, int *cnt);
inline void query(int len, const int4* keys);
void batch_query(int4* sss, int4* eee);


int main(int argc, char *argv[])
{
	init();
	
	tv t1 = get_time();
	batch_query(input, end);
	tv t2 = get_time();
	
	tv t = time_diff(t2, t1);
	
	cout<<t.tv_sec<<", "<<t.tv_usec<<endl;
	
	free(input);
	free(idx1);
	free(invt);
	
	return 0;
}


void init()
{
	input = (int4*) load_file(finput);
	idx1	= (int4*) load_file(fidx1);
	invt	= (int4*) load_file(finvt);
	
	end = input + get_file_size(finput) / sizeof(int4) * sizeof(byte1);
	lst = new int4[MAX_LIST_LEN];
}

inline int intersection(int len1, int4* lst1, int len2, int4* lst2)
{
	int n = 0;
	int pos = 0;
	for(int i = 0; i < len1; i++)
	{
		pos = binary_search(lst1[i], lst2, pos, len2 - 1);
		if(pos >= 0)
			lst1[n++] = lst1[i];
		else
			pos = -pos - 1;	
	}
	
	return n;
}

inline int find_mid(const int tag, int4* arr, int l, int h)
{
	if(tag < arr[l]) return -l -1;
	if(tag > arr[h]) return -h - 1;
	int sp = (int)(1. * tag * h / arr[h]);
	//cout<<sp<<","<<tag<<","<<arr[l]<<","<<l<<endl;
	if(arr[sp] == tag) return sp;
	else if(tag < arr[sp])
		return bw_search(tag, arr, l, sp);
	else return fw_search(tag, arr, sp, h);
}

inline void intersection(int4 *a, int al, int ah, int4 *b, int bl, int bh, int *cnt)
{
	if(al > ah || bl > bh) return;

	int am = (al + ah) / 2, bml, bmr = -1;
	int pos = binary_search(a[am], b, bl, bh);
	
	/*int pos = 0;
	if(bh - bl > 512)
		pos = find_mid(a[am], b, bl, bh);
	else
		pos = binary_search(a[am], b, bl, bh);
	*/
	
	int found = 1;
	// not found
	if(pos < 0)
	{
		pos = -pos - 1;
		found = 0;
		bmr = pos;
	}
	
	bml = pos - 1;
	if(bmr == -1)
		bmr = pos + 1;
	
	intersection(a, al, am - 1, b, bl, bml, cnt);
	
	// found
	if(found == 1)
	{
		a[*cnt] = a[am];
		(*cnt)++;
	}
	
	intersection(a, am + 1, ah, b, bmr, bh, cnt);
}

inline void query(int len, const int4* keys)
{
	for(int i = 0; i < keys[0]; i++)
	{
		lst[i] = *(invt + keys[1] + i);
	}
	
	
	int4 n = keys[0];

	for(int i = 1; i < len; i++)
	{
#define BaezaYates
#ifndef BaezaYates
		n = intersection(n, lst, keys[i * 2], invt + keys[i * 2 + 1]);
#else
		int results = 0;
		intersection(
			lst, 										0, n - 1, 
			invt + keys[i * 2 + 1], 0, keys[i * 2],
			&results);
			n = results;
#endif
	}
	
	/*cout<<"results: "<<n<<endl;
	for(int i = 0; i < n; i++)
	{
		cout<<lst[i]<<endl;
	}*/
}

void batch_query(int4* sss, int4* eee)
{
	while(sss < eee)
	//for(int i = 0; i < 2; i++)
	{
		int n = *sss;
		sss++;
		
		for(int i = 0; i < n; i++)
		{
			int id = *sss;
			sss++;
			items[i * 2] = idx1[id * 2];
			items[i * 2 + 1] = idx1[id * 2 + 1];
		}
		
		query(n, items);
		
		//break;
	}
}

